package brinaryTree;

/**
 * 654. 最大二叉树
 * <p>
 * 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
 * <p>
 * 1. 创建一个根节点，其值为 nums 中的最大值。
 * <p>
 * 2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
 * <p>
 * 3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。
 * <p>
 * 返回 nums 构建的 最大二叉树 。
 */
public class N654_MaxBinaryTree {
    private int[] nums;

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        this.nums = nums;
        return build(0, nums.length - 1);
    }

    private TreeNode build(int left_index, int right_index) {
        if (left_index > right_index) return null;
        int max_index = left_index;
        for (int i = left_index + 1; i <= right_index; i++) {
            if (nums[max_index] < nums[i]) max_index = i;
        }
        TreeNode node = new TreeNode(nums[max_index]);
        node.left = build(left_index, max_index - 1);
        node.right = build(max_index + 1, right_index);
        return node;
    }
}
